package hu;

import java.util.*;

/**
 * 数独题目，回溯 + dfs
 */
public class hu44 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] sudoku = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String[] st = sc.nextLine().split(" ");
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.parseInt(st[j]);
            }
        }
        backtrack(sudoku);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static boolean backtrack(int[][] sudoku){
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(sudoku[i][j] != 0)
                    continue;
                for (int k = 1; k < 10; k++) {
                    if(isValid(i, j, sudoku, k)){
                        sudoku[i][j] = k;
                        if(backtrack(sudoku))
                        return true;
                        // 回溯之处
                        sudoku[i][j] = 0;
                    }
                }
                return false;
            }
        }
        return true;
    }
    public static boolean isValid(int m, int n, int[][] sudoku, int num){
        for (int i = 0; i < 9; i++) {
            if(sudoku[i][n] == num)
                return false;
        }
        for (int i = 0; i < 9; i++) {
            if(sudoku[m][i] == num)
                return false;
        }
        int r = m / 3, c = n / 3;
        for (int i = r * 3; i < r * 3 + 3; i++) {
            for (int j = c * 3; j < c * 3 + 3; j++) {
                if(sudoku[i][j] == num)
                    return false;
            }
        }
        return true;
    }
}
/*
0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1
 */
